We address the following question: When a randomly chosen regular bipartitemulti--graph is drawn in the plane in the ``standard way'', what is thedistribution of its maximum size planar matching (set of non--crossing disjointedges) and maximum size planar subgraph (set of non--crossing edges which mayshare endpoints)? The problem is a generalization of the Longest IncreasingSequence (LIS) problem (also called Ulam's problem). We present combinatorialidentities which relate the number of $r$-regular bipartite multi--graphs withmaximum planar matching (maximum planar subgraph)of at most $d$ edges to asigned sum of restricted lattice walks in $\ZZ^d$, and to the number of pairsof standard Young tableaux of the same shape and with a ``descend--type''property. Our results are obtained via generalizations of two combinatorialproofs through which Gessel's identity can be obtained (an identity that iscrucial in the derivation of a bivariate generating function associated to thedistribution of LISs, and key to the analytic attack on Ulam's problem).
展开▼
机译：我们解决以下问题：当以``标准方式''在平面上绘制随机选择的规则二等图时，其最大尺寸平面匹配（非交叉不交集的集合）和最大尺寸的分布是什么平面子图（可能共享端点的非交叉边的集合）？该问题是最长增加序列（LIS）问题（也称为Ulam问题）的推广。我们提供了组合身份，这些身份将与最大$ d $边的最大平面匹配（最大平面子图）的$ r $-规则二部多图的数量与$ \ ZZ ^ d $中受约束的晶格步移的分配总和相关，并与具有相同形状且具有``下降类型''属性的标准杨氏对数。我们的结果是通过对两个组合证明的概括而获得的，通过该证明可以获得格塞尔身份（在与LIS分布相关的双变量生成函数的推导中至关重要的身份，这是对Ulam问题进行分析攻击的关键）。
展开▼
